package leetcode_day._2023._11;

import java.util.PriorityQueue;

/**
 * 2336.无限集中的最小数字
 * 算法: 设计
 *
 * @author yezh
 * @date 2023/11/29 11:03
 */
public class _29 {

    class SmallestInfiniteSet {

        // 将集合分成两类, 一类是离散的有序数, 另一类是连续的从 idx 开始到 ∞ 的数
        int idx;
        boolean[] vis;
        PriorityQueue<Integer> queue;

        public SmallestInfiniteSet() {
            idx = 1;
            vis = new boolean[1010];
            queue = new PriorityQueue<>();
        }

        public int popSmallest() {
            int val;
            if (!queue.isEmpty()) {
                val = queue.poll();
                vis[val] = false;
            } else val = idx++;
            return val;
        }

        public void addBack(int num) {
            if (num >= idx || vis[num]) return;
            if (num == idx - 1) idx--;
            else if (!vis[num]) {
                queue.offer(num);
                vis[num] = true;
            }
        }
    }

}
